package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;

import cn.edu.jxau.util.LinkedQueue;
import cn.edu.jxau.util.Queue;


/**
 * Kahn拓扑排序算法:寻找入度为0的顶点
 * 初始化入度为0的顶点队列需要遍历整张图，时间复杂度O(V+E)
 * 然后对zeroQueue进行操作，又需要遍历整张图，时间复杂度O(V+E)
 * 所以总的时间复杂度是O(V+E)
 * 
 * @author 付大石
 *
 */
public class KahnTopological {

    public static void main(String[] args) {

        // 有向无环图 //
        DirectedGraph g = new DirectedGraph(13);
        g.addEdge(0, 1);
        g.addEdge(0, 5);
        g.addEdge(0, 6);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 5);
        g.addEdge(5, 4);
        g.addEdge(6, 9);
        g.addEdge(6, 4);
        g.addEdge(7, 6);
        g.addEdge(8, 7);
        g.addEdge(9, 11);
        g.addEdge(9, 10);
        g.addEdge(9, 12);
        g.addEdge(11, 12);
        for (int i : new KahnTopological(g).order()) {
            System.out.print(i + " ");
        }
        // 有向有环图 //
//        DirectedGraph g = new DirectedGraph(6);
//        g.addEdge(0, 5);
//        g.addEdge(5, 4);
//        g.addEdge(4, 3);
//        g.addEdge(3, 5);
//        for (int i : new KahnTopological(g).order()) {
//            System.out.print(i + " ");
//        }
    }

    /**
     * topo排序序列
     */
    private List<Integer> order;

    /**
     * 入度为0的顶点
     */
    private Queue<Integer> zeroQueue;

    /**
     * 记录每个顶点的入度
     */
    private int[] indegreeArr;

    /**
     * 图的边数
     */
    private int e;

    public KahnTopological(DirectedGraph g) {

        order = new ArrayList<>();
        zeroQueue = new LinkedQueue<>();
        indegreeArr = new int[g.v()];
        this.e = g.e();

        // 找出所有入度为0的顶点并将其加入zeroQueue中 //
        for (List<Integer> list : g.adj()) {
            for (Integer i : list) {
                indegreeArr[i]++;
            }
        }
        for(int i=0;i<indegreeArr.length;i++) {
            if(indegreeArr[i] == 0) {
                zeroQueue.enqueue(i);
            }
        }

        // 进行topo排序 //
        sort(g);
    }

    private void sort(DirectedGraph g) {

        while (!zeroQueue.isEmpty()) {
            int v = zeroQueue.dequeue();
            order.add(v);
            for (int w : g.adj(v)) {
                e--;
                if (--indegreeArr[w] == 0) {
                    zeroQueue.enqueue(w);
                }
            }
        }
        if (e != 0) {
            throw new RuntimeException("有向有环图无法进行topological排序");
        }
    }

    /**
     * 返回topo排序的序列
     * @return
     */
    public Iterable<Integer> order() {
        return order;
    }
}
